首先我们说这道题是线段树（其实只是不会二分而已）
既然是线段树，那么我们首先当然是最简单的建树
建树代码如下
1 | void build(int p,int l,int r) |
此处只需要查询区间最小值，所以建树是很基础的，就不多赘述了。
接下来是更新1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25void add(int p,int l,int r,long long d)
{
if(f==1)
return;
if(a[p].left==l&&a[p].right==r)
{
a[p].val+=d;
a[p].num+=d;
if(a[p].num<0)
f=1;
return;
}
pushdown(p);
int mid=(a[p].left+a[p].right)/2;
if(r<=mid)
add(2*p,l,r,d);
else if(l>mid)
add(2*p+1,l,r,d);
else
{
add(2*p,l,mid,d);
add(2*p+1,mid+1,r,d);
}
pushup(p);
}
值得注意的是此处的标记是为了优化，如果不加就会T掉一个点
最后查询的时候只需查询根节点的区间最小值，只需查标记就可以了（但是先要更新）
总代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using namespace std;
struct node
{
int left,right;
long long val,num;
};struct node a[4*N];
int data[N],n,m,x,y,z,b,f;
void pushup(int p)
{
a[p].num=min(a[2*p].num,a[2*p+1].num);
}
void pushdown(int p)
{
if(a[p].val!=0)
{
a[2*p].val+=a[p].val;
a[2*p+1].val+=a[p].val;
a[2*p].num+=a[p].val;
a[2*p+1].num+=a[p].val;
a[p].val=0;
}
}
void build(int p,int l,int r)
{
a[p].left=l;
a[p].right=r;
if(l==r)
{
a[p].num=data[l];
return;
}
int mid=(a[p].left+a[p].right)/2;
build(2*p,l,mid);
build(2*p+1,mid+1,r);
pushup(p);
}
void add(int p,int l,int r,long long d)
{
if(f==1)
return;
if(a[p].left==l&&a[p].right==r)
{
a[p].val+=d;
a[p].num+=d;
if(a[p].num<0)
f=1;
return;
}
pushdown(p);
int mid=(a[p].left+a[p].right)/2;
if(r<=mid)
add(2*p,l,r,d);
else if(l>mid)
add(2*p+1,l,r,d);
else
{
add(2*p,l,mid,d);
add(2*p+1,mid+1,r,d);
}
pushup(p);
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&data[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&z);
add(1,y,z,-x);
if(f==1)
{
printf("-1\n%d",i);
return 0;
}
}
printf("0");
return 0;
}
虽然说是卡线段树，但其实并不会（虽然3448ms跑的比较慢）
总还是可以A